﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace GraphControl
{
    public class BasicGraph
    {
        public List<Vertex> vertices { get; set; }


        public BasicGraph()
        {
            vertices = new List<Vertex>();
        }

        public Vertex findVertex(string name)
        {
            Vertex foundVertex = null;
            foreach (Vertex v in vertices)
            {
                if (v.Name.Equals(name))
                    foundVertex = v;
            }
            return foundVertex;
        }

        public bool IsEmpty()
        {
            return vertices.Count == 0;
        }
        public bool IsAdjacencies(Vertex vertex1, Vertex vertex2)
        {
            List<Edge> edges = vertices[vertices.IndexOf(vertex1)].Edges;
            bool found = false;
            int i = 0;

            while (i < edges.Count && !found)
                if (edges[i].To == vertex2)
                    found = true;
                else
                    i++;
            return found;
        }


        public void AddVertex(Vertex item)
        {
            vertices.Add(item);
        }

        public void addEdge(Vertex from, Vertex to)
        {
            Edge ed = new Edge(from, to, 1);
            from.AddEdge(ed);
            to.AddEdge(ed);
        }

        private Edge FindEdge(Vertex from, Vertex to)
        {
            Edge result = null;
            int size = -1;
            bool found = false;
            while (!found && ++size < from.Edges.Count)
            {
                if (from.Edges[size].To.Equals(to))
                {
                    result = from.Edges[size];
                    found = true;
                }
            }
            return result;
        }

        public void RemoveVertex(Vertex vertex)
        {
            vertices.Remove(vertex);
        }

        public void RemoveEdge(Vertex from, Vertex to)
        {
            List<Edge> edges = vertices[vertices.IndexOf(from)].Edges;

            bool found = false;
            int i = 0;

            while (i < edges.Count && !found)
                if (edges[i].To == to)
                {
                    edges.RemoveAt(i);
                    found = true;
                }

                else
                    i++;
        }

        public int NumberOfAdjacencies(Vertex vertex)
        {
            if (vertices.Contains(vertex))
                return vertices[vertices.IndexOf(vertex)].Edges.Count;

            else
                return 0;
        }

        public List<Vertex> GetAdjacencies(Vertex vertex)
        {
            List<Vertex> vertexList = new List<Vertex>();

            foreach (Edge edge in vertices[vertices.IndexOf(vertex)].Edges)
                vertexList.Add(edge.To);

            return vertexList;
        }

        public void Empty()
        {
            vertices.Clear();
        }


        public List<Vertex> GetAllVertexesByBreadthFirst(Vertex startVertex)
        {
            ClearMarks();

            List<Vertex> resultList = new List<Vertex>();

            Queue<Vertex> q = new Queue<Vertex>(vertices.Count);
            q.Enqueue(startVertex);
            startVertex.Mark = true;

            while (q.Count > 0)
            {
                resultList.Add(q.Dequeue());

                foreach (Vertex v in GetAdjacencies(resultList[resultList.Count - 1]))
                {
                    if (!v.Mark)
                    {
                        q.Enqueue(v);
                        v.Mark = true;
                    }
                }
            }

            ClearMarks();

            return resultList;
        }

        public void ClearMarks()
        {
            foreach (Vertex v in vertices)
            {
                v.Mark = false;
            }
        }

        public List<Vertex> GetAllVertexesByDepthFirst(Vertex startVertex)
        {
            List<Vertex> resultList = new List<Vertex>();
            resultList.Add(startVertex);
            startVertex.Mark = true;

            foreach (Vertex v in GetAdjacencies(startVertex))
                if (!v.Mark)
                    resultList.AddRange(GetAllVertexesByDepthFirst(v));

            return resultList;
        }
    }
}
